<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Document</title>
</head>

<body>
  <script>//环境配置，算法代码不在这里，请从51行开始阅读
    //一些常量，可以自定义修改
    const WIDTH = 100;
    const HEIGHT = 80;
    //不建议修改的常量
    const RED = "#FF0000";
    const GREEN = "#00FF00";
    const BLUE = "#0000FF";
    //parpare environment:
    let h31 = document.createElement('h3');
    h31.innerHTML = 'DDA ';
    h31.style.color = BLUE;
    h31.style.textAlign = 'center';
    document.body.appendChild(h31);
    let h32 = document.createElement('h3');
    h32.innerHTML = '中点画线算法(改进) ';
    h32.style.color = GREEN;
    h32.style.textAlign = 'center';
    document.body.appendChild(h32);
    let h33 = document.createElement('h3');
    h33.innerHTML = '改进的Bresenham画线算法';
    h33.style.color = RED;
    h33.style.textAlign = 'center';
    document.body.appendChild(h33);

    const el = document.createElement('canvas');
    el.id = 'canvas';
    el.width = WIDTH << 2;
    el.height = HEIGHT << 2;
    el.style = 'border: 1px solid #000; display: block; margin: 0 auto';
    document.body.appendChild(el);

    const ctx = el.getContext('2d');

    function point(x, y) { 
      ctx.fillRect(x << 2, (HEIGHT - y) << 2, 4, 4);
      console.log('create a point (' + x + ',' + y + ')');
    }
  </script>
  <script>//算法代码在这，main函数在305行
    //DDA
    function dda(x1, y1, x2, y2) {// 用dda方法绘制(x1,y1),(x2,y2)这条直线
      if (x1 === x2) {//特殊情况：没有k的时候
        let min = Math.min(y1, y2);
        let max = Math.max(y1, y2);
        for (let i = min; i <= max; i++) {
          point(x1, i);
        }
        return;
      }
      if (y1 === y2) {//特殊情况：没有k的时候
        let min = Math.min(x1, x2);
        let max = Math.max(x1, x2);
        for (let i = min; i <= max; i++) {
          point(i, y1);
        }
        return;
      }
      let k = (y2 - y1) / (x2 - x1);
      let x = 0;
      let y = 0;
      let temp = 0;
      if (Math.abs(k) > 1) {// |k|>1
        if (y1 > y2) {//调整1，2的位置，使y1一定要小于y2
          temp = y1;
          y1 = y2;
          y2 = temp;
          temp = x1;
          x1 = x2;
          x2 = temp;
        }
        k = (x2 - x1) / (y2 - y1);
        x = x1;
        for (y = y1; y <= y2; y++) {
          point(Math.trunc(x + 0.5), y);
          x = x + k;
        }
      } else {//|k|<=1
        if (x1 > x2) {//调整1，2的位置，使x1一定要小于x2
          temp = y1;
          y1 = y2;
          y2 = temp;
          temp = x1;
          x1 = x2;
          x2 = temp;
        }
        y = y1;
        for (x = x1; x <= x2; x++) {
          point(x, Math.trunc(y + 0.5));
          y = y + k;
        }
      }
    }

    //中点画线算法
    function midpolet(x1, y1, x2, y2) { //用中点画线算法绘制(x1,y1),(x2,y2)这条直线
      if (x1 === x2) {//处理特殊情况，k不存在
        let min = Math.min(y1, y2);
        let max = Math.max(y1, y2);
        for (let i = min; i <= max; i++) {
          point(x1, i);
        }
        return;
      }
      if (y1 === y2) {//处理特殊情况，k不存在
        let min = Math.min(x1, x2);
        let max = Math.max(x1, x2);
        for (let i = min; i <= max; i++) {
          point(i, y1);
        }
        return;
      }
      let a, b, d1, d2, d, x, y, m;
      if (x2 < x1) {//确保x1是小于x2的
        d = x1;
        x1 = x2;
        x2 = d;
        d = y1;
        y1 = y2;
        y2 = d;
      }
      a = y1 - y2;
      b = x2 - x1;
      if (b === 0) m = -1 * a * 100;
      else m = a / (x1 - x2);
      x = x1;
      y = y1;
      point(x, y);
      if (m >= 0 && m <= 1) {//k:[0,1]
        d = 2 * a + b;
        d1 = 2 * a;
        d2 = 2 * (a + b);
        while (x < x2) {
          if (d <= 0) {
            x++;
            y++;
            d += d2;
          } else {
            x++;
            d += d1;
          }
          point(x, y);
        }
      } else if (m <= 0 && m >= -1) {//k:[-1,0]
        d = 2 * a - b;
        d1 = 2 * a - 2 * b;
        d2 = 2 * a;
        while (x < x2) {
          if (d > 0) {
            x++;
            y--;
            d += d1;
          } else {
            x++;
            d += d2;
          }
          point(x, y);
        }
      } else if (m > 1) {//k:(1,∞)
        d = a + 2 * b;
        d1 = 2 * (a + b);
        d2 = 2 * b;
        while (y < y2) {
          if (d > 0) {
            x++;
            y++;
            d += d1;
          } else {
            y++;
            d += d2;
          }
          point(x, y);
        }
      } else {//k:(-∞,-1)
        d = a - 2 * b;
        d1 = -2 * b;
        d2 = 2 * (a - b);
        while (y > y2) {
          if (d <= 0) {
            x++;
            y--;
            d += d2;
          } else {
            y--;
            d += d1;
          }
          point(x, y);
        }
      }
    }

    //Bresenham
    function bresenham(x1, y1, x2, y2) { //用bresenham算法绘制(x1,y1),(x2,y2)这条直线
      if (x1 === x2) {//特殊情况的处理，k不存在的时候
        let min = Math.min(y1, y2);
        let max = Math.max(y1, y2);
        for (let i = min; i <= max; i++) {
          point(x1, i);
        }
        return;
      }
      if (y1 === y2) {//处理特殊情况，k不存在的时候
        let min = Math.min(x1, x2);
        let max = Math.max(x1, x2);
        for (let i = min; i <= max; i++) {
          point(i, y1);
        }
        return;
      }
      let x, y, dx, dy, e;
      dx = x2 - x1;
      dy = y2 - y1;
      ddx = dx<<1;//这里只是为了存一下2倍的值，不至于一直要计算，下同
      ddy = dy<<1;
      x = x1;
      y = y1;
      if ((dx >= 0 && dy >= 0) || (dx <= 0 && dy <= 0)) {//dx,dy同号
        if ((dx < 0) || (dx === 0 && dy < 0)) {
          dx = -dx;
          x = x2;
          dy = -dy;
          y = y2;
        }
        if (dy < dx) {
          e = -dx;
          for (let i = 0; i < dx; i++) {
            point(x, y);
            x++;
            e = e + ddy;
            if (e >= 0) {
              y++;
              e = e - ddx;
            }
          }
        } else {
          e = -dy;
          for (let i = 0; i < dy; i++) {
            point(x, y);
            y++;
            e = e + ddx;
            if (e >= 0) {
              x++;
              e = e - ddy;
            }
          }
        }
      } else {//dx,dy异号
        let tempx, tempy;
        if (dx < 0) {
          tempx = -dx;
          tempy = dy;
        }
        if (dy < 0) {
          tempx = dx;
          tempy = -dy;
        }
        if (tempx > tempy) {
          if (dx < 0) {
            dx = -dx;
            x = x2;
            dy = -dy;
            y = y2;
          }
          e = -dx;
          for (let i = 0; i < dx; i++) {
            point(x, y);
            x++;
            e = e - ddy;
            if (e >= 0) {
              y--;
              e -= ddx;
            }
          }
        } else {
          if (dy < 0) {
            dx = -dx;
            x = x2;
            dy = -dy;
            y = y2;
          }
          e = -dy;
          for (let i = 0; i < dy; i++) {
            point(x, y);
            y++;
            e -= ddx;
            if (e >= 0) {
              x--;
              e -= ddy;
            }
          }
        }
      }
    }

    //main
    ctx.fillStyle = BLUE;
    dda(5, 20, 25, 30);// 用dda方法绘制(x1,y1),(x2,y2)这条直线
    ctx.fillStyle = GREEN;
    midpolet(5, 20, 25, 30);//用中点画线算法绘制(x1,y1),(x2,y2)这条直线
    ctx.fillStyle = RED;
    bresenham(5, 20, 25, 30);//用bresenham算法绘制(x1,y1),(x2,y2)这条直线
  </script>
</body>

</html>